home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Internet Tools 1993 July / Internet Tools.iso / RockRidge / mail / smail-3.1.28 / src / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-07-11  |  44.0 KB  |  1,463 lines
  1. /* @(#)src/hash.c    1.5 7/11/92 11:49:16 */
  2.  
  3. /*
  4.  *    Copyright (C) 1987, 1988 Ronald S. Karr and Landon Curt Noll
  5.  *    Copyright (C) 1992  Ronald S. Karr
  6.  * 
  7.  * See the file COPYING, distributed with smail, for restriction
  8.  * and warranty information.
  9.  */
  10.  
  11. /*
  12.  * hash:
  13.  *    perform a string hashing algorithm functions
  14.  *
  15.  *     Hash tables are defined by their size.  It is suggested that the
  16.  *     size be a prime value, say:
  17.  *        13, 29, 47, 61, 113, 181, 251, 359, 509, 751, 1021, 1511,
  18.  *        2039, 3079, 4093, 6151, 8179, 12377, 16381, 24571, 32749,
  19.  *        49139, 65557, 98299, 132049, 180023, 216091, 321367, 521539, ...
  20.  *     An advantage with the above primes is that they are at last 3 less
  21.  *     than 2^n, and no closer than 3 away from 3*(2^m) for the larger 
  22.  *     values of m.  Most malloc systems are most efficient when one allocates
  23.  *     3 words less than 2^n bytes, i.e., 4*(2^n - 3) bytes.
  24.  *
  25.  *    external functions:
  26.  *        add_to_hash, lookup_in_hash, delete_from_hash,
  27.  *        delete_from_hash, store_in_hash, new_hash_table,
  28.  *        write_hash_table, walk_hash, free_hash_element,
  29.  *        free_hash_table
  30.  */
  31. #include <stdio.h>
  32. #include <ctype.h>
  33. #include "smail.h"
  34. #include "defs.h"
  35. #include "exitcodes.h"
  36. #include "hash.h"
  37. #include "alloc.h"
  38. #ifndef DEPEND
  39. # include "extern.h"
  40. # include "debug.h"
  41. #endif
  42.  
  43. /* static functions used in this file */
  44. static int hash_str();
  45. static int hash_stric();
  46. static struct hash *new_hash_element();
  47.  
  48. #ifdef STANDALONE
  49. int debug = 0;    /* default debug level is NONE */
  50. #define errfile stderr
  51. void panic();
  52. #define xmalloc(x) (malloc(x))    /* naive allocator */
  53. #define bmalloc(x,y) (malloc(x))    /* naive allocator */
  54. char *malloc();
  55. #define xfree(x) (free(x))    /* naive deallocator */
  56. #define bfree(x,y) (free(x))    /* naive deallocator */
  57. void free();
  58. #endif    /* STANDALONE */
  59.  
  60. /*
  61.  * ETHEREAL_HASHDATA -
  62.  *
  63.  *    This file contains a nearly complete implementation of a general
  64.  *    hashing system.  However it is likely that smail itself will
  65.  *    never need to delete, replace, or store new data over old data.
  66.  *    That is, smail will only create, add, lookup and perform hash
  67.  *    table file operations.
  68.  *
  69.  *    The code ifdef-ed out does work and is tested by the STANDALONE code.
  70.  *    You should define ETHEREAL_HASHDATA if you want to use it
  71.  */
  72.  
  73.  
  74. /*
  75.  * hash_str - convert a trying into a hash value
  76.  *
  77.  * We build the hash value one character at a time by repeating the following
  78.  * steps for each character:
  79.  *
  80.  *    1) The previous value is shifted up (by HASH_UP_SHIFT) and the
  81.  *       current character is added
  82.  *    2) any upper level excess bits are fetched (by masking with
  83.  *       {H,L}_HASH_MASK) and xor-ed into bits near the bottom
  84.  *    3) the upper level excess bits are cleared
  85.  *
  86.  * In the end, the hash value is taken modulo `mod' to produce a slot number.
  87.  *
  88.  * input:
  89.  *    str    - string to hash
  90.  *    mod    - number of hash table entries
  91.  * output:
  92.  *    the slot number on which `str' belongs
  93.  *
  94.  * NOTE: For more optimal hashing of smaller hash tables (entries < HASH_LEVEL)
  95.  *       we L_ value constants.  This gives us a faster hash fold.  For larger
  96.  *     hash tables, this is not needed so H_ value constants are used.
  97.  *
  98.  * NOTE: mod should be a prime <= ~H_HASH_MASK
  99.  */
  100. static int
  101. hash_str(str, mod)
  102.     register char *str;            /* the string to hash */
  103.     int mod;                /* prime modulus, size of hash table */
  104. {
  105.     register unsigned long val;        /* current hash value */
  106.     register unsigned long excess;    /* upper/excess bits in val */
  107.     register unsigned long c;        /* the current string character */
  108.  
  109.     /* firewall - bogus case, but be safe anyway */
  110.     if (str == NULL) {
  111.     return 0;
  112.     }
  113.  
  114.     /*
  115.      * hash each character in the string
  116.      *
  117.      * if our mod is small enough, then use L_ value constants so that
  118.      * strings can fold into themselves faster.
  119.      */
  120.     if (mod < HASH_LEVEL) {
  121.     /* hash each character using the L_ values */
  122.     for (val = 0; c=(unsigned long)*str; ++str) {
  123.         val = (val << HASH_UP_SHIFT) + c;
  124.         val ^= ((excess = (val&L_HASH_MASK)) >> L_DOWN_SHIFT);
  125.         val ^= excess;
  126.     }
  127.     } else {
  128.     /* hash each character using the H_ values */
  129.     for (val = 0; c=(unsigned long)*str; ++str) {
  130.         val = (val << HASH_UP_SHIFT) + c;
  131.         val ^= ((excess = (val&H_HASH_MASK)) >> H_DOWN_SHIFT);
  132.         val ^= excess;
  133.     }
  134.     }
  135.     
  136.     return (int)(val%mod);    /* our hash value, mod the hash size */
  137. }
  138.  
  139. /*
  140.  * hash_stric - convert a trying into a hash value without regard to case
  141.  *
  142.  * We build the hash value one character at a time by repeating the following
  143.  * steps for each character:
  144.  *
  145.  *    1) The previous value is shifted up (by HASH_UP_SHIFT) and the
  146.  *       current character is added
  147.  *    2) any upper level excess bits are fetched (by masking with
  148.  *       {H,L}_HASH_MASK) and xor-ed into bits near the bottom
  149.  *    3) the upper level excess bits are cleared
  150.  *
  151.  * In the end, the hash value is taken modulo `mod' to produce a slot number.
  152.  *
  153.  * input:
  154.  *    str    - string to hash without regard to case
  155.  *    mod    - number of hash table entries
  156.  * output:
  157.  *    the slot number on which `str' belongs
  158.  *
  159.  * NOTE: For more optimal hashing of smaller hash tables (entries < HASH_LEVEL)
  160.  *       we L_ value constants.  This gives us a faster hash fold.  For larger
  161.  *     hash tables, this is not needed so H_ value constants are used.
  162.  *
  163.  * NOTE: mod should be a prime <= ~H_HASH_MASK
  164.  */
  165. static int
  166. hash_stric(str, mod)
  167.     register char *str;        /* the string to hash disregarding case */
  168.     int mod;            /* prime modulus, size of hash table */
  169. {
  170.     register unsigned long val;        /* current hash value */
  171.     register unsigned long excess;    /* upper/excess bits in val */
  172.     register unsigned long c;        /* the current string character */
  173.  
  174.     /* firewall - bogus case, but be safe anyway */
  175.     if (str == NULL) {
  176.     return 0;
  177.     }
  178.  
  179.     /*
  180.      * hash each character in the string
  181.      *
  182.      * if our mod is small enough, then use L_ value constants so that
  183.      * strings can fold into themselves faster.
  184.      */
  185.     if (mod < HASH_LEVEL) {
  186.     /* hash each character using the L_ values */
  187.     for (val = 0; c=(unsigned long)lowercase(*str); ++str) {
  188.         val = (val << HASH_UP_SHIFT) + c;
  189.         val ^= ((excess = (val&L_HASH_MASK)) >> L_DOWN_SHIFT);
  190.         val ^= excess;
  191.     }
  192.     } else {
  193.     /* hash each character using the H_ values */
  194.     for (val = 0; c=(unsigned long)lowercase(*str); ++str) {
  195.         val = (val << HASH_UP_SHIFT) + c;
  196.         val ^= ((excess = (val&H_HASH_MASK)) >> H_DOWN_SHIFT);
  197.         val ^= excess;
  198.     }
  199.     }
  200.     
  201.     return (int)(val%mod);    /* our hash value, mod the hash size */
  202. }
  203.  
  204.  
  205. #ifdef ETHEREAL_HASHDATA
  206. /*
  207.  * walk_hash - walk thru a hash table
  208.  *
  209.  * returns NULL if there is no next element in the hash table
  210.  *
  211.  * input:
  212.  *    cur    - our current location, or NULL to start at the beginning
  213.  *    table    - the table to be walked
  214.  * output:
  215.  *    a pointer to the next element, or NULL if no next element
  216.  *
  217.  * WARNING: results will be unpredictable or fatal if `cur' != NULL, and
  218.  *        `cur' != `the previous walk location', and `cur' is an element
  219.  *        that has been either deleted or replaced by another element.
  220.  *        It should be noted that this `cur' will never be the `previous
  221.  *        walk location' if our previous call ran off the end of the table.
  222.  */
  223. struct hash *
  224. walk_hash(cur, table)
  225.     struct hash *cur;        /* where we are now */
  226.     struct hash_table *table;    /* hash table being walked */
  227. {
  228.     register struct hash *prev;    /* our previous walk location */
  229.     register int indx;        /* our previous hash slot */
  230.     register int len;        /* the table length */
  231.  
  232.     /*
  233.      * firewall
  234.      */
  235.     if (table == NULL) {
  236.     panic(EX_SOFTWARE, "walk_hash: table is NULL");
  237.     }
  238.     /* fetch these values for faster use */
  239.     prev = table->prev;
  240.     indx = table->indx;
  241.     len = table->len;
  242.  
  243.     /*
  244.      * find the first hash slot if cur is NULL (due to a restart request)
  245.      */
  246.     if (cur == NULL) {
  247.     /* note that we really don't have a location yet */
  248.     prev = NULL;
  249.  
  250.     /* find the first slot and return it */
  251.     for (indx=0; indx < len; ++indx) {
  252.         if (full_slot(table->slot[indx])) {
  253.         /* we found the first entry of the first non-empty chain */
  254.         prev = table->slot[indx];
  255.         break;
  256.         }
  257.     }
  258.  
  259.     /*
  260.      * walk from our current location to the next location
  261.      */
  262.     } else {
  263.  
  264.     /*
  265.      * if `cur' is not the previous `cur', then find `cur' and
  266.      * note where our hash table index now resides
  267.      */
  268.     if (cur != prev) {
  269.         /* find the hash table index */
  270.         indx = hash_string(cur->keystr, len, table->flags&HASH_CASEFOLD);
  271.         /* if `cur' is an empty slot, panic */
  272.         if (empty_slot(table->slot[indx])) {
  273.             panic(EX_SOFTWARE, "walk_hash: <%s> hash slot is empty",
  274.               cur->keystr);
  275.         }
  276.     
  277.         /* walk down the hash table chain looking for our entry */
  278.         for (prev = table->slot[indx];
  279.          cur != prev && prev != NULL;
  280.          prev = next_hash(prev,table)) {
  281.         }
  282.     }
  283.     /* if `cur' is not in the hash table, panic */
  284.     if (prev == NULL) {
  285.         panic(EX_SOFTWARE, "walk_hash: <%s> is not in table", cur->keystr);
  286.     }
  287.  
  288.     /*
  289.      * if we were at the end of a chain, then our successor will
  290.      * be the start of the next non-empty chain
  291.      */
  292.     if ((prev = next_hash(prev,table)) == NULL) {
  293.         /* find the next non-empty chain */
  294.         for (++indx; indx < len; ++indx) {
  295.         if (full_slot(table->slot[indx])) {
  296.             /* return first element of this chain */
  297.             prev = table->slot[indx];
  298.             break;
  299.             }
  300.         }
  301.     }
  302.     }
  303.  
  304.     /*
  305.      * return the pointer the next element or NULL
  306.      */
  307.     /* remember our location for next time */
  308.     table->prev = hash_addr(prev, table);
  309.     table->indx = indx;
  310.     return table->prev;
  311. }
  312. #endif    /* ETHEREAL_HASHDATA */
  313.  
  314.  
  315. /*
  316.  * new_hash_element - creat a new hash element
  317.  *
  318.  * return a malloced new hash element with the lengths correctly filled out
  319.  *
  320.  * inputs:
  321.  *    keystr    - the key of this data element
  322.  *    data    - the data to accompany `keystr', or NULL if no data
  323.  *    datalen    - the length of `data' in bytes, or 0 is no data
  324.  *    table    - the hash table which will get this element
  325.  */
  326. static struct hash *
  327. new_hash_element(keystr, data, datalen, table)
  328.     char *keystr;                /* the keystring to be added */
  329.     char *data;                /* the associated data if any */
  330.     int datalen;            /* length of data,  0 ==> no data */
  331.     struct hash_table *table;        /* hash table being added to */
  332. {
  333.     struct hash *new;        /* the new slot chain location */
  334.     int keylen;            /* the length of the string, padded */
  335.     unsigned long lk;        /* temp var for key length */
  336.  
  337.     /*
  338.      * firewall - check for bad pointers and values
  339.      */
  340.     if (keystr == NULL || table == NULL) {
  341.     panic(EX_SOFTWARE, "new_hash_element: NULL keystring or table");
  342.     }
  343.     lk = keystr_len(keystr);        /* compute padded key length */
  344.     if (lk >= (unsigned long)(1L<<BITS_PER_SHORT)) {
  345.     panic(EX_SOFTWARE, "new_hash_element: key too long");
  346.     }
  347.     keylen = (int)lk;        /* now we know it will fit in an int */
  348.     /* firewall - check against bad data being passed to us */
  349.     if (datalen < 0 || (datalen > 0 && data == NULL) || 
  350.       (unsigned long)datalen >= (unsigned long)(1L<<BITS_PER_SHORT))  {
  351.     panic(EX_SOFTWARE,
  352.         "new_hash_element: bad data passed with: <%s>  datalen: <%d>",
  353.         keystr, datalen);
  354.     }
  355.  
  356.     /*
  357.      * malloc the storage
  358.      */
  359.     new = (struct hash *)bmalloc( hashslot_size(keylen,datalen), table->life );
  360.     /* firewall */
  361.     if (is_odd(new)) {
  362.     panic(EX_SOFTWARE,
  363.           "new_hash_element: malloc returned odd address: %lx",
  364.           (long)new);
  365.     }
  366.  
  367.     /*
  368.      * return the prebuild element
  369.      */
  370.     new->succ = NULL;
  371.     new->keylen = keylen;
  372.     strcpy(new->keystr, keystr);
  373.     new->datalen = datalen;
  374.     if (datalen > 0) {
  375.     memcpy(hash_data(new), data, datalen);
  376.     }
  377.     return new;
  378. }
  379.  
  380. #ifdef ETHEREAL_HASHDATA
  381. /*
  382.  * free_hash_element - free an old hash element
  383.  *
  384.  * Frees a hash table element according to the life of the hash table.
  385.  * Removes the hash table element if it in the hash table unless explicitly
  386.  * told that the element is not in the table.
  387.  *
  388.  * inputs:
  389.  *    cur    - the element which which we will free
  390.  *    search    - non-zero means delete `cur' from table prior to the free
  391.  *    table    - the table on which `cur' resides, or the table to which
  392.  *          `cur' would have been added
  393.  *
  394.  * WARNING: It is important that the `cur' element NOT be in a hash table
  395.  *        after the free.  Unpredictable results will happen otherwise.
  396.  *        If `search' is non-zero, we will first attempt to delete `cur'
  397.  *        from `table'.  It is a fatal error if `search' is non-zero and
  398.  *        `cur' is not in `table'.
  399.  *
  400.  * WARNING: It is important that `cur' was individually malloced (perhaps
  401.  *        by new_hash_element) so that the free of its address will
  402.  *        be valid.
  403.  */
  404. void
  405. free_hash_element(cur, search, table)
  406.     struct hash *cur;        /* what we will delete */
  407.     int search;            /* non-zero => delete `cur' first */
  408.     struct hash_table *table;    /* table `cur' does/would_have belonged to */
  409. {
  410.     /*
  411.      * firewall - check for bad pointers and values
  412.      */
  413.     if (cur == NULL || table == NULL) {
  414.     panic(EX_SOFTWARE, "free_hash_element: NULL cur or table");
  415.     }
  416.  
  417.     /*
  418.      * delete the element first if requested
  419.      */
  420.     if (search != 0 && delete_from_hash(cur->keystr, table) == NULL) {
  421.     panic(EX_SOFTWARE,"free_hash_element: <%s> not in table",cur->keystr);
  422.     }
  423.  
  424.     /*
  425.      * free the storage
  426.      */
  427.     bfree(cur, table->life);
  428.     return;
  429. }
  430. #endif    /* ETHEREAL_HASHDATA */
  431.  
  432. /*
  433.  * new_hash_table - creat a new hash table
  434.  *
  435.  * return a malloced new hash table with correctly setup initial pointers
  436.  *
  437.  * input:
  438.  *    tablelen - number of slots in the hash table
  439.  *    life - the alloc block to which this is to be associated, or NULL
  440.  *           meaning the permanent block
  441.  * output:
  442.  *    a pointer to a malloced empty hash table
  443.  */
  444. struct hash_table *
  445. new_hash_table(tablelen, life, flags)
  446.     int tablelen;        /* number of slots in the hash table */
  447.     struct block *life;        /* is the hash table permanent or temporary */
  448.     int flags;            /* hash table flag as per struct hash_table */
  449. {
  450.     register int i;            /* index */
  451.     struct hash_table *table;        /* the malloced hash table */
  452.  
  453.     /*
  454.      * firewalls
  455.      */
  456.     if (tablelen <= 0) {
  457.     panic(EX_SOFTWARE, "new_hash_table: tablelen: %d", tablelen);
  458.     }
  459.     DEBUG3(DBG_HASH_LO,
  460.        "new_hash_table: tablelen:%d life:%d flag:%d\n",tablelen,life,flags);
  461.  
  462.     /*
  463.      * malloc the hash table
  464.      */
  465.     table = (struct hash_table *)bmalloc(table_size(tablelen), life);
  466.     /* firewall */
  467.     if (is_odd(table)) {
  468.     panic(EX_SOFTWARE,
  469.         "new_hash_table: malloc returned odd address: %d", (int)table);
  470.     }
  471.  
  472.     /*
  473.      * initialize the table
  474.      */
  475.     table->len = tablelen;
  476.     table->flags = flags & HASH_FLAGMASK;
  477.     table->life = life;
  478.     table->prev = NULL;        /* no current walk_hash() location */
  479.     table->indx = 0;        /* no current walk_hash() slot index */
  480.     for (i=0; i < tablelen; i++) {
  481.     table->slot[i] = NULL;
  482.     }
  483.     return table;    /* return our new table */
  484. }
  485.  
  486. #ifdef ETHEREAL_HASHDATA
  487. /*
  488.  * free_hash_table - free a hash table and its associated data
  489.  *
  490.  * Free all storage associated with a hash table.
  491.  *
  492.  * NOTE: any malloced elements should be freed prior to calling this routine.
  493.  *
  494.  * input:
  495.  *    table    - the hash table to free
  496.  */
  497. void
  498. free_hash_table(table)
  499.     struct hash_table *table;    /* the hash table to free */
  500. {
  501.     struct hash *cur;        /* current element to delete */
  502.  
  503.     /*
  504.      * firewalls
  505.      */
  506.     if (table == NULL ) {
  507.     panic(EX_SOFTWARE, "free_hash_table: NULL table");
  508.     }
  509.     DEBUG(DBG_HASH_LO,"free_hash_table: start\n");
  510.  
  511.     /*
  512.      * free the table slots
  513.      */
  514.     bfree(table, table->life);
  515.     return;
  516. }
  517. #endif    /* ETHEREAL_HASHDATA */
  518.  
  519.  
  520. /*
  521.  * add_to_hash - add an element to the a hash table
  522.  *
  523.  * inputs:
  524.  *    keystr    - the key of the data to add
  525.  *    data    - the data to accompany `keystr', or NULL if no data
  526.  *    datalen    - the length of `data' in bytes, or 0 if no data
  527.  *    table    - a pointer to the hash table which is being modified
  528.  * output:
  529.  *    returns ALREADY_HASHED if `keystr' is already in the `table', or
  530.  *    JUST_HASHED if we just added a no key.  The `table' is not modified
  531.  *    if the key is already exists.
  532.  */
  533. int
  534. add_to_hash(keystr, data, datalen, table)
  535.     char *keystr;                /* the keystring to be added */
  536.     char *data;                /* the associated data if any */
  537.     int datalen;            /* length of data,  0 ==> no data */
  538.     struct hash_table *table;        /* the hash table to add it to */
  539. {
  540.     register struct hash *cur;        /* the current slot chain location */
  541.     register struct hash *prev;        /* the previous slot chain location */
  542.     register int cmp;            /* -1, 0, or 1 for < = > compare */
  543.     register int caseflag;        /* 0 ==> use strcmp, 1 ==> strcmpic */
  544.     int loc;                /* the hash slot to add onto */
  545.     struct hash *new;            /* the new slot chain location */
  546.  
  547.     /*
  548.      * firewall - watch for NULLs
  549.      */
  550.     if (keystr == NULL) {
  551.     panic(EX_SOFTWARE, "add_to_hash: NULL keystr");
  552.     }
  553.     if (table == NULL) {
  554.     panic(EX_SOFTWARE, "add_to_hash: NULL table");
  555.     }
  556.  
  557.     /*
  558.      * determine the slot on which this entry is to be added
  559.      */
  560.     caseflag = table->flags & HASH_CASEFOLD;
  561.     loc = hash_string(keystr, table->len, caseflag);
  562.     DEBUG2(DBG_HASH_LO, "add_to_hash: keystr: <%s> slot: %d\n", keystr, loc);
  563.  
  564.     /*
  565.      * search the slot chain for our entry
  566.      */
  567.     /* special case for empty slot chains */
  568.     if (empty_slot(table->slot[loc])) {
  569.     DEBUG(DBG_HASH_MID, "add_to_hash: insert in NULL slot\n");
  570.     new = new_hash_element(keystr, data, datalen, table);
  571.     insert_hash(&table->slot[loc], new);
  572.     return JUST_HASHED;
  573.     }
  574.  
  575.     /* 
  576.      * search the chain
  577.      */
  578.     DEBUG2(DBG_HASH_VHI, "add_to_hash: slot:0x%lx cur:0x%lx\n",
  579.        (long)table->slot[loc], (long)table->slot[loc]);
  580.     for (prev=NULL, cur=table->slot[loc];
  581.      cur != NULL; prev=cur, cur=next_hash(cur,table)) {
  582.     /* 
  583.      * if we found the entry, stop
  584.      */
  585.     DEBUG2(DBG_HASH_VHI, "add_to_hash: comparing <%s> to <%s>",
  586.            keystr, cur->keystr);
  587.     if ((cmp = stringcmp(keystr, cur->keystr, caseflag)) == 0) {
  588.         DEBUG(DBG_HASH_MID, "add_to_hash: already hashed\n");
  589.         return ALREADY_HASHED;
  590.  
  591.     /* 
  592.      * we are past the insertion point, insert before here and stop
  593.      * note if we are inserting at the beginning a a chain or in the middle
  594.      */
  595.     } else if (cmp < 0) {
  596.         new = new_hash_element(keystr, data, datalen, table);
  597.         if (prev == NULL) {
  598.         DEBUG(DBG_HASH_MID, "add_to_hash: insert at front\n");
  599.         insert_hash(&table->slot[loc], new);  /* insert at beginning */
  600.         } else {
  601.         DEBUG(DBG_HASH_MID, "add_to_hash: insert in middle\n");
  602.         insert_hash(prev, new);    /* insert in middle */
  603.         }
  604.         return JUST_HASHED;
  605.     }
  606.     }
  607.  
  608.     /* 
  609.      * case: insertion at the end of the chain
  610.      */
  611.     DEBUG(DBG_HASH_MID, "add_to_hash: insert at END\n");
  612.     new = new_hash_element(keystr, data, datalen, table);
  613.     insert_hash(prev, new);
  614.     return JUST_HASHED;
  615. }
  616.  
  617. #ifdef ETHEREAL_HASHDATA
  618. /*
  619.  * replace_in_hash - replace an existing element in a hash table
  620.  *
  621.  * inputs:
  622.  *    keystr    - the key of the data to replace
  623.  *    data    - the data to accompany `keystr', or NULL if no data
  624.  *    datalen    - the length of `data' in bytes, or 0 if no data
  625.  *    table    - a pointer to the hash table which is being modified
  626.  * output:
  627.  *    returns a pointer to the element that was replaced, or NULL
  628.  *    if no element was replaced due to `keystr' not in `table'
  629.  */
  630. struct hash *
  631. replace_in_hash(keystr, data, datalen, table)
  632.     char *keystr;                /* the keystring to replace */
  633.     char *data;                /* the associated data if any */
  634.     int datalen;            /* length of data,  0 ==> no data */
  635.     struct hash_table *table;        /* the hash table to add it to */
  636. {
  637.     register struct hash *cur;        /* the current slot chain location */
  638.     register struct hash *prev;        /* the previous slot chain location */
  639.     register int cmp;            /* -1, 0, or 1 for < = > compare */
  640.     register int caseflag;        /* 0 ==> use strcmp, 1 ==> strcmpic */
  641.     int loc;                /* the hash slot to add onto */
  642.     struct hash *new;            /* the new slot chain location */
  643.  
  644.     /*
  645.      * firewall - watch for NULLs
  646.      */
  647.     if (keystr == NULL) {
  648.     panic(EX_SOFTWARE, "replace_in_hash: NULL keystr");
  649.     }
  650.     if (table == NULL) {
  651.     panic(EX_SOFTWARE, "replace_in_hash: NULL table");
  652.     }
  653.  
  654.     /*
  655.      * determine the slot on which this entry is to be added
  656.      */
  657.     caseflag = table->flags & HASH_CASEFOLD;
  658.     loc = hash_string(keystr, table->len, caseflag);
  659.     DEBUG2(DBG_HASH_LO, "replace_in_hash: keystr: <%s> slot: %d\n",keystr,loc);
  660.  
  661.     /*
  662.      * search the slot chain for our entry
  663.      */
  664.     /* special case for empty slow chains */
  665.     if (empty_slot(table->slot[loc])) {
  666.     DEBUG(DBG_HASH_MID, "replace_in_hash: slot NULL\n");
  667.     return NULL;    /* no entry to replace */
  668.     }
  669.  
  670.     /* 
  671.      * search the chain
  672.      */
  673.     for (prev=NULL, cur=table->slot[loc]; cur != NULL; 
  674.       prev=cur, cur=next_hash(cur, table)) {
  675.     /* 
  676.      * if we found the entry, stop
  677.      */
  678.     if ((cmp = stringcmp(keystr, cur->keystr, caseflag)) == 0) {
  679.         new = new_hash_element(keystr, data, datalen, table);
  680.         if (prev == NULL) {
  681.         DEBUG(DBG_HASH_MID, "replace_in_hash: replaced at front\n");
  682.         /* insert at beginning */
  683.         replace_hash(table->slot[loc], cur, new);
  684.         } else {
  685.         DEBUG(DBG_HASH_MID, "replace_in_hash: replaced in middle\n");
  686.         replace_hash(prev->succ, cur, new);    /* insert in middle */
  687.         }
  688.         return cur;
  689.     /* if we have gone past our entry, stop searching */
  690.         } else if (cmp < 0) {
  691.         break;
  692.     }
  693.     }
  694.  
  695.     /* 
  696.      * entry not found, nothing to replace
  697.      */
  698.     DEBUG(DBG_HASH_MID, "replace_in_hash: not found\n");
  699.     return NULL;
  700. }
  701.  
  702. /*
  703.  * store_in_hash - store an existing element in a hash table
  704.  *
  705.  * inputs:
  706.  *    keystr    - the key of the data to store
  707.  *    data    - the data to accompany `keystr', or NULL if no data
  708.  *    datalen    - the length of `data' in bytes, or 0 if no data
  709.  *    table    - a pointer to the hash table which is being modified
  710.  * output:
  711.  *    returns a pointer to the element that was replaced, or NULL
  712.  *    if no element was replaced.  In any case the element is added.
  713.  */
  714. struct hash *
  715. store_in_hash(keystr, data, datalen, table)
  716.     char *keystr;                /* the keystring to replace */
  717.     char *data;                /* the associated data if any */
  718.     int datalen;            /* length of data,  0 ==> no data */
  719.     struct hash_table *table;        /* the hash table to add it to */
  720. {
  721.     register struct hash *cur;        /* the current slot chain location */
  722.     register struct hash *prev;        /* the previous slot chain location */
  723.     register int cmp;            /* -1, 0, or 1 for < = > compare */
  724.     register int caseflag;        /* 0 ==> use strcmp, 1 ==> strcmpic */
  725.     int loc;                /* the hash slot to add onto */
  726.     struct hash *new;            /* the new slot chain location */
  727.  
  728.     /*
  729.      * firewall - watch for NULLs
  730.      */
  731.     if (keystr == NULL) {
  732.     panic(EX_SOFTWARE, "store_in_hash: NULL keystr");
  733.     }
  734.     if (table == NULL) {
  735.     panic(EX_SOFTWARE, "store_in_hash: NULL table");
  736.     }
  737.  
  738.     /*
  739.      * determine the slot on which this entry is to be added
  740.      */
  741.     caseflag = table->flags & HASH_CASEFOLD;
  742.     loc = hash_string(keystr, table->len, caseflag);
  743.     DEBUG2(DBG_HASH_LO, "store_in_hash: keystr: <%s> loc: %d\n", keystr, loc);
  744.  
  745.     /*
  746.      * search the slot chain for our entry
  747.      */
  748.     /* special case for empty slow chains */
  749.     if (empty_slot(table->slot[loc])) {
  750.     DEBUG(DBG_HASH_MID, "store_in_hash: insert on NULL slot\n");
  751.     new = new_hash_element(keystr, data, datalen, table);
  752.     insert_hash(&table->slot[loc], new);
  753.     return NULL;
  754.     }
  755.  
  756.     /* 
  757.      * search the chain
  758.      */
  759.     for (prev=NULL, cur=table->slot[loc]; cur != NULL; 
  760.       prev=cur, cur=next_hash(cur, table)) {
  761.     /* 
  762.      * if we found the entry, stop
  763.      */
  764.     if ((cmp = stringcmp(keystr, cur->keystr, caseflag)) == 0) {
  765.         new = new_hash_element(keystr, data, datalen, table);
  766.         if (prev == NULL) {
  767.         DEBUG(DBG_HASH_MID, "store_in_hash: replaced at front\n");
  768.         /* insert at beginning */
  769.         replace_hash(table->slot[loc], cur, new);
  770.         } else {
  771.         DEBUG(DBG_HASH_MID, "store_in_hash: replaced in middle\n");
  772.         replace_hash(prev->succ, cur, new);    /* insert in middle */
  773.         }
  774.         return cur;
  775.  
  776.     /* 
  777.      * we are past the insertion point, insert before here and stop
  778.      * note if we are inserting at the beginning a a chain or in the middle
  779.      */
  780.     } else if (cmp < 0) {
  781.         new = new_hash_element(keystr, data, datalen, table);
  782.         if (prev == NULL) {
  783.         DEBUG(DBG_HASH_MID, "store_in_hash: insert at front\n");
  784.         insert_hash(&table->slot[loc], new);  /* insert at beginning */
  785.         } else {
  786.         DEBUG(DBG_HASH_MID, "store_in_hash: insert in middle\n");
  787.         insert_hash(&prev->succ, new);    /* insert in middle */
  788.         }
  789.         return NULL;
  790.     }
  791.     }
  792.  
  793.     /* 
  794.      * case: insertion at the end of the chain
  795.      */
  796.     DEBUG(DBG_HASH_MID, "store_in_hash: insert at END\n");
  797.     new = new_hash_element(keystr, data, datalen, table);
  798.     insert_hash(&prev->succ, new);
  799.     return NULL;
  800. }
  801. #endif    /* ETHEREAL_HASHDATA */
  802.  
  803. /*
  804.  * lookup_in_hash - lookup an element in a hash table and return 
  805.  *            the associated data
  806.  *
  807.  * inputs:
  808.  *    keystr    - the key of the data to add
  809.  *    data    - pointer to a pointer, or 0 if no data is wanted
  810.  *    datalen    - pointer to the data length, or NULL if no length is wanted
  811.  *    table    - a pointer to the hash table which is being modified
  812.  * output:
  813.  *    returns ALREADY_HASHED if `keystr' is already in the `table', or
  814.  *        NOT_HASHED the key was not found
  815.  *    data    - if `data' was non-NULL points at the key's data or NULL
  816.  *          no data
  817.  *    datalen    - if `datalen' was non-NULL, points at the length of the
  818.  *          key's data
  819.  */
  820. int
  821. lookup_in_hash(keystr, data, datalen, table)
  822.     char *keystr;            /* the key to lookup */
  823.     char **data;            /* where to point at data, or NULL */
  824.     int *datalen;            /* where to place data len or NULL */
  825.     struct hash_table *table;        /* the hash table to add it to */
  826. {
  827.     register struct hash *cur;    /* the slot chain location */
  828.     int loc;            /* the hash slot to add onto */
  829.     int caseflag;        /* 0 ==> use strcmp, 1 ==> strcmpic */
  830.     int cmp;            /* compare function result */
  831.  
  832.     /*
  833.      * firewall - watch for NULLs
  834.      */
  835.     if (keystr == NULL) {
  836.     panic(EX_SOFTWARE, "lookup_in_hash: NULL keystr");
  837.     }
  838.     if (table == NULL) {
  839.     panic(EX_SOFTWARE, "lookup_in_hash: table is NULL");
  840.     }
  841.  
  842.     /*
  843.      * determine the hash slot to search on
  844.      */
  845.     caseflag = table->flags & HASH_CASEFOLD;
  846.     loc = hash_string(keystr, table->len, caseflag);
  847.     DEBUG2(DBG_HASH_LO, "lookup_in_hash: keystr: <%s> slot: %d\n",keystr,loc);
  848.     /* watch out for empty chains, there is nothing on them */
  849.     if (empty_slot(table->slot[loc])) {
  850.     DEBUG(DBG_HASH_MID, "lookup_in_hash: found at slot END\n");
  851.     return NOT_HASHED;
  852.     }
  853.  
  854.     /* 
  855.      * search the chain
  856.      */
  857.     for (cur=table->slot[loc]; cur != NULL; cur=next_hash(cur, table)) {
  858.     /*
  859.      * if we found the entry, stop
  860.      */
  861.     if ((cmp = stringcmp(keystr, cur->keystr, caseflag)) == 0) {
  862.         DEBUG(DBG_HASH_MID, "lookup_in_hash: found\n");
  863.         /*
  864.          * fill in the requested args
  865.          */
  866.         if (data != NULL) {
  867.         *data = hash_data(cur);    
  868.         }
  869.         if (datalen != NULL) {
  870.         *datalen = cur->datalen;
  871.         }
  872.         return ALREADY_HASHED;
  873.     /* if we have gone past our entry, stop searching */
  874.         } else if (cmp < 0) {
  875.         break;
  876.     }
  877.     }
  878.  
  879.     /* found nothing */
  880.     DEBUG(DBG_HASH_MID, "lookup_in_hash: not found\n");
  881.     return NOT_HASHED;
  882. }
  883.  
  884. #ifdef ETHEREAL_HASHDATA
  885. /*
  886.  * delete_from_hash - delete an element in the hash table
  887.  *
  888.  * inputs:
  889.  *    keystr    - the key of the data to add
  890.  *    table    - a pointer to the hash table which is being modified
  891.  * output:
  892.  *    returns a pointer to the element that was deleted, or NULL
  893.  *    if no element was deleted due to `keystr' not in `table'
  894.  */
  895. struct hash *
  896. delete_from_hash(keystr, table)
  897.     char *keystr;            /* the key to lookup */
  898.     struct hash_table *table;        /* the hash table to add it to */
  899. {
  900.     register struct hash *cur;        /* the slot chain location */
  901.     register struct hash *prev;        /* previous element */
  902.     int loc;            /* the hash slot to add onto */
  903.     int caseflag;        /* 0 ==> use strcmp, 1 ==> strcmpic */
  904.     int cmp;            /* compare function result */
  905.  
  906.     /*
  907.      * firewall - watch for NULLs
  908.      */
  909.     if (keystr == NULL) {
  910.     panic(EX_SOFTWARE, "delete_from_hash: keystr is NULL");
  911.     }
  912.     if (table == NULL) {
  913.     panic(EX_SOFTWARE, "delete_from_hash: table is NULL");
  914.     }
  915.  
  916.     /*
  917.      * determine the hash slot to search on
  918.      */
  919.     caseflag = table->flags & HASH_CASEFOLD;
  920.     loc = hash_string(keystr, table->len, caseflag);
  921.     DEBUG2(DBG_HASH_LO, "delete_from_hash: keystr: <%s> loc: %d\n",keystr,loc);
  922.     /* watch out for empty chains, there is nothing on them */
  923.     if (empty_slot(table->slot[loc])) {
  924.     DEBUG(DBG_HASH_MID, "delete_from_hash: EMPTY slot\n");
  925.     return NULL;    /* key is not in the table */
  926.     }
  927.  
  928.     /* 
  929.      * search the chain for the element to delete
  930.      */
  931.     for (prev=NULL, cur=table->slot[loc]; cur != NULL; 
  932.       prev=cur, cur=next_hash(cur, table)) {
  933.     /* 
  934.      * if we found the entry, stop
  935.      */
  936.     if ((cmp = stringcmp(keystr, cur->keystr, caseflag)) == 0) {
  937.         if (prev == NULL) {
  938.         DEBUG(DBG_HASH_MID, "delete_from_hash: delete at front\n");
  939.         /* delete at the beginning */
  940.         delete_hash(&table->slot[loc], cur);
  941.         } else {
  942.         DEBUG(DBG_HASH_MID, "delete_from_hash: delete in middle\n");
  943.         delete_hash(&prev->succ, cur);    /* delete in middle */
  944.         }
  945.         return cur;
  946.     /*
  947.      * if we have gone past the entry, stop looking
  948.      */
  949.         } else if (cmp < 0) {
  950.         DEBUG(DBG_HASH_MID, "delete_from_hash: past spot\n");
  951.         break;
  952.         }
  953.     }
  954.  
  955.     /* found nothing */
  956.     DEBUG(DBG_HASH_MID, "delete_from_hash: not found\n");
  957.     return NULL;        /* nothing was deleted */
  958. }
  959. #endif    /* ETHEREAL_HASHDATA */
  960.  
  961.  
  962. /*
  963.  * write_hash_table - write a hash table to a stream
  964.  *
  965.  * input:
  966.  *    tab    - the hash table to write
  967.  *    stream    - the stream on which to write
  968.  */
  969. void
  970. write_hash_table(table, stream)
  971.     struct hash_table *table;    /* the table to write */
  972.     FILE *stream;        /* the stream on which to write table */
  973. {
  974.     register int i;        /* index */
  975.     long tab_loc;        /* file location of hash_table start */
  976.     long loc;            /* current location */
  977.     int size;            /* size of the current element */
  978.     long offset;                /* current offset within the file */
  979.     long disc_succ;             /* cur->succ as written to disc */
  980.     struct hash *cur;        /* the current hash element */
  981.     struct hash_table *tab;    /* disk copy of table */
  982.  
  983.     /*
  984.      * firewalls
  985.      */
  986.     if (table == NULL || stream == NULL) {
  987.     panic(EX_SOFTWARE, "write_hash_table: NULL arguments");    
  988.     }
  989.     if (table->len <= 0) {
  990.     panic(EX_SOFTWARE, "write_hash_table: table length: %d", table->len);
  991.     }
  992.     DEBUG2(DBG_HASH_LO, "write_hash_table: size: %d life: %d\n",
  993.        table->len, table->life);
  994.  
  995.     /*
  996.      * allocate a temporary disk copy of the hash table
  997.      */
  998.     tab = (struct hash_table *)xmalloc(table_size(table->len));
  999.     tab->life = table->life;        /* preserve life type */
  1000.     tab->len = table->len;        /* preserve table length */
  1001.     tab->flags = table->flags;        /* preserve flags - XXX all bits ??? */
  1002.     tab->prev = NULL;            /* clear walking location */
  1003.     tab->indx = 0;            /* clear walking slot index */
  1004.  
  1005.     /*
  1006.      * skip the hash table block
  1007.      */
  1008.     tab_loc = ftell(stream);
  1009.     if (fseek(stream, (long)table_size(table->len), 1) < 0) {
  1010.     panic(EX_IOERR, "write_hash_table: bad skip of %d over table",
  1011.         table_size(table->len));
  1012.     }
  1013.  
  1014.     /*
  1015.      * write out each hash table chain
  1016.      */
  1017.     for (i=0; i < table->len; i++) {
  1018.  
  1019.     /* don't write out chains that don't exist */
  1020.     if (empty_slot(table->slot[i])) {
  1021.         /* slot is empty, deal with it quickly */
  1022.         set_ptr(tab->slot[i], (int)NULL);
  1023.         continue;
  1024.     }
  1025.  
  1026.     /* note starting offset of hash chain */
  1027.     offset = ftell(stream) - tab_loc;
  1028.     if (is_odd(offset)) {
  1029.         panic(EX_IOERR, "write_hash_table: slot %d offset is odd:%ld",
  1030.               i, offset);
  1031.     }
  1032.     set_ptr(tab->slot[i], to_odd(offset));
  1033.  
  1034.     /* write up to the last chain element */
  1035.     for (cur=table->slot[i]; cur != NULL; cur=next_hash(cur, table)) {
  1036.         /* compute the current element length */
  1037.         size = hash_len(cur);
  1038.         if (is_odd(size)) {
  1039.             panic(EX_IOERR,
  1040.               "write_hash_table: size is odd:%ld for <%s>",
  1041.               offset, cur->keystr);
  1042.         }
  1043.         offset += size;        /* note file movement */
  1044.         /* write the hash element disk successor element */
  1045.         disc_succ = (cur->succ == NULL) ? 0 : to_odd(offset);
  1046.         if (fwrite((char *)&disc_succ, sizeof(disc_succ), 1, stream) != 1) {
  1047.         panic(EX_IOERR,
  1048.               "write_hash_table: bad succ write <%s> on slot %d",
  1049.               cur->keystr, i);
  1050.         }
  1051.         /* write the rest of the hash element data */
  1052.         if (fwrite((char *)cur+sizeof(cur->succ), size-sizeof(cur->succ),
  1053.                1, stream) != 1) {
  1054.         panic(EX_IOERR,
  1055.               "write_hash_table: bad write <%s> on slot %d",
  1056.               cur->keystr, i);
  1057.         }
  1058.     }
  1059.     }
  1060.  
  1061.     /*
  1062.      * write the hash table back in its place and return to our
  1063.      * current position
  1064.      */
  1065.     loc = ftell(stream);    /* remember our current location */
  1066.     if (fseek(stream, (long)tab_loc, 0) < 0) {
  1067.     panic(EX_IOERR, "write_hash_table: bad skip back to table at %d",
  1068.         tab_loc);
  1069.     }
  1070.     if (fwrite((char *)tab, table_size(tab->len), 1, stream) != 1) {
  1071.     panic(EX_IOERR, "write_hash_table: bad table write");
  1072.     }
  1073.     if (fseek(stream, (long)loc, 0) < 0) {
  1074.     panic(EX_IOERR, "write_hash_table: bad end seek to %d", loc);
  1075.     }
  1076.  
  1077.     /*
  1078.      * free the temporary disk copy of the hash table
  1079.      */
  1080.     xfree((char *)tab);
  1081.     return;
  1082. }
  1083.  
  1084.  
  1085. #ifdef STANDALONE
  1086.  
  1087. #include "varargs.h"
  1088. #include <sys/types.h>
  1089. #include <sys/stat.h>
  1090.  
  1091. #define TABLE_LEN 3 /* use only a few slots to stress the chain code */
  1092. #define INPUT_SIZE (70*1024)    /* max input line */
  1093.  
  1094. char *tempname = "/tmp/hashtestXXXXXX";    /* tempory hash file name */
  1095.  
  1096. void
  1097. main(argc, argv)
  1098.     int argc;    /* arg count */
  1099.     char *argv[];     /* args */
  1100. {
  1101.     int i;            /* index */
  1102.     char buf[INPUT_SIZE+1];    /* the input buffer for stdin args */
  1103.     struct hash *cur;        /* pointer to walk the table */
  1104.     struct hash_table *table;    /* our allocated table */
  1105.     struct hash_table *tableic;    /* allocated table without regard to case */
  1106.     void test();        /* test an with an element */
  1107.     void dump_hash_table();    /* dump the contents of the hash table */
  1108.     void hash_file_test();    /* perform hash file testing */
  1109.  
  1110.     /*
  1111.      * establish debug level
  1112.      */
  1113.     DEBUG(DBG_HASH_LO, "main: start\n");
  1114.     if (argc > 1 && strncmp(argv[1], "-d", 2) == 0) {
  1115.         /* we have a debug level, use it */
  1116.         if (argv[1][2] != '\0') {
  1117.             debug = atoi(&argv[1][2]);
  1118.             --argc;
  1119.             ++argv;
  1120.         } else if (argc > 2) {
  1121.             debug = atoi(argv[2]);
  1122.             argc -= 2;
  1123.             argv += 2;
  1124.         }
  1125.     }
  1126.     DEBUG1(DBG_HASH_LO, "main: debug level: %d\n", debug);
  1127.  
  1128.     /*
  1129.      * setup a hash table
  1130.      */
  1131.     table = new_hash_table(TABLE_LEN, (struct block *)NULL, HASH_CASEFOLD);
  1132.     tableic = new_hash_table(TABLE_LEN, (struct block *)NULL, 0);
  1133.  
  1134.     /*
  1135.      * special case: no args means read one arg per line
  1136.      */
  1137.     if (argc == 1) {
  1138.     while(fgets(buf, INPUT_SIZE, stdin) != NULL) {
  1139.         i = strlen(buf);
  1140.         buf[i-1] = '\0';
  1141.         DEBUG1(DBG_HASH_LO,
  1142.            "main: testing <%s> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\n", buf);
  1143.         test(buf, table);
  1144.         if ( debug >= DBG_HASH_HI ) {
  1145.         dump_hash_table(table);
  1146.         }
  1147.         DEBUG1(DBG_HASH_LO,
  1148.            "main: testing ignore case <%s> -*-*-*-*-*-*-*-*-*-\n", buf);
  1149.         test(buf, tableic);
  1150.         if ( debug >= DBG_HASH_HI ) {
  1151.         dump_hash_table(tableic);
  1152.         }
  1153.     }
  1154.  
  1155.     /*
  1156.      * hash each argument
  1157.      */
  1158.     } else {
  1159.     for (i=1; i < argc; ++i) {
  1160.         DEBUG1(DBG_HASH_LO,
  1161.            "main: testing <%s> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\n", buf);
  1162.         test(argv[i], table);
  1163.         if ( debug >= DBG_HASH_HI ) {
  1164.         dump_hash_table(table);
  1165.         }
  1166.         DEBUG1(DBG_HASH_LO,
  1167.            "main: testing ignore case <%s> -*-*-*-*-*-*-*-*-*-\n", buf);
  1168.         test(argv[i], tableic);
  1169.         if ( debug >= DBG_HASH_HI ) {
  1170.         dump_hash_table(tableic);
  1171.         }
  1172.     }
  1173.     }
  1174.  
  1175.     /*
  1176.      * test the file operations
  1177.      */
  1178.     DEBUG(DBG_HASH_LO, "main: hash_file_test\n");
  1179.     hash_file_test(table);
  1180.     DEBUG(DBG_HASH_LO, "main: hash_file_test ignore case\n");
  1181.     hash_file_test(tableic);
  1182.  
  1183.     /*
  1184.      * final cleanup
  1185.      */
  1186.     DEBUG(DBG_HASH_LO, "main: free memory\n");
  1187.     /* free the hash table elements */
  1188.     for (cur=walk_hash((struct hash *)NULL,table);
  1189.      cur != NULL;
  1190.      cur=walk_hash(cur,table))
  1191.     {
  1192.     free_hash_element(cur, 0, table); /* free without deletion */
  1193.     }
  1194.     free_hash_table(table);    /* free up the memory */
  1195.     DEBUG(DBG_HASH_LO, "main: free memory ignore case\n");
  1196.     for (cur=walk_hash((struct hash *)NULL,tableic);
  1197.      cur != NULL;
  1198.      cur=walk_hash(cur,tableic))
  1199.     {
  1200.     free_hash_element(cur, 0, tableic); /* free without deletion */
  1201.     }
  1202.     free_hash_table(tableic);    /* free up the memory */
  1203.     DEBUG(DBG_HASH_LO, "main: end\n");
  1204.     exit(EX_OK);
  1205. }
  1206.  
  1207. /*
  1208.  * perform various tests on a string
  1209.  */
  1210. void
  1211. test(buf, table)
  1212.     char *buf;        /* the key to add */
  1213.     struct hash_table *table;    /* our allocated table */
  1214. {
  1215.     register struct hash *cur;    /* the current hash entry */
  1216.     char *data;            /* the data we stored */
  1217.     int datalen;        /* length of data */
  1218.     int buflen;            /* length of the buffer string + NULL */
  1219.     int i;            /* index */
  1220.     register int caseflag;    /* 0 ==> use strcmp, 1 ==> strcmpic */
  1221.  
  1222.     /* test adding */
  1223.     buflen = strlen(buf)+1;
  1224.     i = add_to_hash(buf, buf, buflen, table);
  1225.     DEBUG2(DBG_HASH_LO, "test: <%s> add: %d\n", buf, i);
  1226.  
  1227.     /* test the lookup function */
  1228.     DEBUG1(DBG_HASH_MID, "test: <%s> lookup\n", buf);
  1229.     caseflag = table->flags & HASH_CASEFOLD;
  1230.     if (lookup_in_hash(buf, &data, &datalen, table) != ALREADY_HASHED) {
  1231.     panic(EX_SOFTWARE,
  1232.           "test: add_to_hash lost <%s>", buf);
  1233.     } else if (stringcmp(buf, data, caseflag) != 0 || buflen != datalen) {
  1234.     panic(EX_SOFTWARE,
  1235.           "test: add_to_hash lookup <%s> != <%s>", buf, data);
  1236.     }
  1237.     i = add_to_hash(buf, buf, buflen, table);
  1238.     if (i != ALREADY_HASHED) {
  1239.     panic(EX_SOFTWARE, "test: add_to_hash returned: %d for #2\n", i);
  1240.     }
  1241.  
  1242.     /* test the delete function */
  1243.     DEBUG1(DBG_HASH_MID, "test: <%s> delete\n", buf);
  1244.     cur = delete_from_hash(buf, table);    /* delete something that exists */
  1245.     if (cur == NULL) {
  1246.     panic(EX_SOFTWARE,
  1247.           "test: delete_from_hash unable to delete <%s>", buf);
  1248.     } else if (stringcmp(buf, hash_data(cur), caseflag) != 0 ||
  1249.            buflen != cur->datalen) {
  1250.     panic(EX_SOFTWARE,
  1251.           "test: delete_from_hash mis delete of <%s>", buf);
  1252.     } else {
  1253.     free_hash_element(cur, 0, table); /* free up memory */
  1254.     }
  1255.     DEBUG1(DBG_HASH_MID, "test: <%s> empty delete\n", buf);
  1256.     cur = delete_from_hash(buf, table);    /* delete a nothing */
  1257.     if (cur != NULL) {
  1258.     panic(EX_SOFTWARE,
  1259.           "test: delete_from_hash ghost delete #2 of <%s>", buf);
  1260.     }
  1261.  
  1262.     /* test the store function */
  1263.     DEBUG1(DBG_HASH_MID, "test: <%s> store\n", buf);
  1264.     cur = store_in_hash(buf, buf, buflen, table);
  1265.     if (cur != NULL) {
  1266.     panic(EX_SOFTWARE,
  1267.           "test: store_in_hash ghost store of <%s>", buf);
  1268.     }
  1269.     DEBUG1(DBG_HASH_MID, "test: <%s> store #2\n", buf);
  1270.     cur = store_in_hash(buf, buf, buflen, table);
  1271.     if (cur == NULL) {
  1272.     panic(EX_SOFTWARE,
  1273.           "test: store_in_hash lost store #2 of <%s>", buf);
  1274.     } else if (stringcmp(buf, hash_data(cur), caseflag) != 0 ||
  1275.            buflen != cur->datalen) {
  1276.     panic(EX_SOFTWARE,
  1277.           "test: store_in_hash mis store #2 of <%s>", buf);
  1278.     } else {
  1279.     free_hash_element(cur, 0, table); /* free up memory */
  1280.     }
  1281.     
  1282.     /* test the replace function */
  1283.     DEBUG1(DBG_HASH_MID, "test: <%s> replace_in_hash\n", buf);
  1284.     cur = replace_in_hash(buf, buf, buflen, table);
  1285.     if (cur == NULL) {
  1286.     panic(EX_SOFTWARE,
  1287.           "test: replace_in_hash lost <%s>", buf);
  1288.     } else if (stringcmp(buf, hash_data(cur), caseflag) != 0 ||
  1289.            buflen != cur->datalen) {
  1290.     panic(EX_SOFTWARE,
  1291.           "test: replace_in_hash mis replace of <%s>", buf);
  1292.     } else {
  1293.     free_hash_element(cur, 0, table); /* free up memory */
  1294.     }
  1295.     DEBUG1(DBG_HASH_MID, "test: <%s> replace_in_hash empty\n", buf);
  1296.     cur = delete_from_hash(buf, table);    /* delete something that exists */
  1297.     if (cur == NULL) {
  1298.     panic(EX_SOFTWARE,
  1299.           "test: delete_from_hash unable to delete #3 <%s>", buf);
  1300.     } else {
  1301.     free_hash_element(cur, 0, table); /* free up memory */
  1302.     }
  1303.     cur = replace_in_hash(buf, buf, buflen, table);
  1304.     if (cur != NULL) {
  1305.     panic(EX_SOFTWARE,
  1306.           "test: replace_in_hash ghost replace of <%s>", buf);
  1307.     } else {
  1308.     /* put it back for keeps */
  1309.     cur = store_in_hash(buf, buf, buflen, table);
  1310.     if (cur != NULL) {
  1311.         panic(EX_SOFTWARE,
  1312.           "test: store_in_hash store #3 lost <%s>", buf);
  1313.         }
  1314.     }
  1315. }
  1316.  
  1317. /*
  1318.  * dump_hash_table - dump the hash table
  1319.  */
  1320. void
  1321. dump_hash_table(table)
  1322.     struct hash_table *table;    /* our allocated table */
  1323. {
  1324.     int i;                /* index */
  1325.     struct hash *cur;        /* the current hash entry */
  1326.  
  1327.     /*
  1328.      * check the hash chains
  1329.      */
  1330.     for (i=0; i < TABLE_LEN; ++i) {
  1331.     DEBUG1(DBG_HASH_HI, "dump: slot[%d]:", i);
  1332.     /* check for empty slots */
  1333.     if (empty_slot(table->slot[i])) {
  1334.         DEBUG(DBG_HASH_HI, "Empty\n");
  1335.         continue;
  1336.     }
  1337.     for (cur=table->slot[i]; cur != NULL; cur=next_hash(cur, table)) {
  1338.         if (cur->keylen == 0) {
  1339.         DEBUG2(DBG_HASH_HI, " 0x%lx: <%s> :EOC ",
  1340.            (long)cur, cur->keystr);
  1341.         } else {
  1342.         DEBUG3(DBG_HASH_HI, " 0x%lx: <%s> :0x%lx ",
  1343.            (long)cur, cur->keystr, (long)cur->succ);
  1344.         }
  1345.     }
  1346.     DEBUG(DBG_HASH_HI, "\n");
  1347.     }
  1348. }
  1349.  
  1350. /*
  1351.  * hash_file_test - test the hash table file operations
  1352.  */
  1353. void
  1354. hash_file_test(table)
  1355.     struct hash_table *table;        /* the hash table to operate on */
  1356. {
  1357.     char *filename;        /* the file to operate on */
  1358.     struct stat buf;        /* file status buffer */
  1359.     struct hash *cur;        /* current location in hash table */
  1360.     struct hash *cur2;        /* current location in hash table2 */
  1361.     struct hash_table *table2;    /* the hash table to operate on */
  1362.     int caseflag;        /* 0 ==> use strcmp, 1 ==> strcmpic */
  1363.     char *template;        /* template for mktemp */
  1364.     FILE *stream;        /* the file stream */
  1365.     char *mktemp();        /* form a temp filename */
  1366.  
  1367.     /*
  1368.      * open up a file to perform hash table operations into
  1369.      */
  1370.     template = xmalloc(strlen(tempname)+1);
  1371.     strcpy(template, tempname);
  1372.     filename = mktemp(template);
  1373.     DEBUG1(DBG_HASH_LO, "hash_file_test: using <%s>\n", filename);
  1374.     stream = fopen(filename, "w");
  1375.     if (stream == NULL) {
  1376.     panic(EX_CANTCREAT, "hash_file_test: can not creat <%s>", filename);
  1377.     }
  1378.  
  1379.     /*
  1380.      * write out the hash table
  1381.      */
  1382.     write_hash_table(table, stream);
  1383.     if (fclose(stream) != 0) {
  1384.     panic(EX_IOERR, "hash_file_test: can not fclose\n");
  1385.     }
  1386.  
  1387.     /*
  1388.      * reread the hash table into memory
  1389.      */
  1390.     DEBUG1(DBG_HASH_MID, "hash_file_test: rereading <%s>\n", filename);
  1391.     stream = fopen(filename, "r");
  1392.     if (stream == NULL) {
  1393.     panic(EX_CANTCREAT, "hash_file_test: can not reopen <%s>", filename);
  1394.     }
  1395.     if (fstat(fileno(stream), &buf) < 0) {
  1396.     panic(EX_IOERR, "hash_file_test: can not stat <%s>", filename);
  1397.     }
  1398.     table2 = (struct hash_table *)xmalloc(buf.st_size * sizeof(char));
  1399.     if (fread((char *)table2,sizeof(char),buf.st_size,stream) != buf.st_size) {
  1400.     panic(EX_IOERR, "hash_file_test: can not reread <%s>", filename);
  1401.     }
  1402.  
  1403.     /*
  1404.      * walk thru each hash table and verify string/data
  1405.      */
  1406.     caseflag = table->flags & HASH_CASEFOLD;
  1407.     DEBUG(DBG_HASH_MID, "hash_file_test: verify\n");
  1408.     for (cur=walk_hash((struct hash *)NULL,table),
  1409.          cur2=walk_hash((struct hash *)NULL,table2);
  1410.      cur != NULL || cur2 != NULL;
  1411.      cur=walk_hash(cur,table), cur2=walk_hash(cur2,table2))
  1412.     {
  1413.         /* compare cur and cur2 */
  1414.         if (stringcmp(cur->keystr,cur2->keystr,caseflag) != 0) {
  1415.         panic(EX_SOFTWARE,
  1416.               "hash_file_test: key mismatch: <%s> != <%s>\n",
  1417.               cur->keystr, cur2->keystr);
  1418.         }
  1419.         if (cur->datalen != cur2->datalen) {
  1420.         panic(EX_SOFTWARE,
  1421.               "hash_file_test: key mismatch: %d != %d\n",
  1422.               cur->datalen, cur2->datalen);
  1423.         }
  1424.         if (memcmp(hash_data(cur), hash_data(cur2), cur->datalen) != 0) {
  1425.         panic(EX_SOFTWARE,
  1426.               "hash_file_test: data mismatch between <%s> and <%s>\n",
  1427.               cur->keystr, cur2->keystr);
  1428.         }
  1429.     }
  1430.  
  1431.     /*
  1432.      * cleanup
  1433.      */
  1434.     DEBUG(DBG_HASH_MID, "hash_file_test: cleanup\n");
  1435.     xfree(table2);
  1436. }
  1437.  
  1438. /*
  1439.  * panic - fake the panic routine
  1440.  *
  1441.  * define panic rather than using the external routines.
  1442.  */
  1443. /*VARARGS2*/
  1444. void
  1445. panic(exitcode, fmt, va_alist)
  1446.     int exitcode;            /* call exit(exitcode) */
  1447.     char *fmt;                /* printf(3) format */
  1448.     va_dcl                              /* arguments for printf */
  1449. {
  1450.     va_list ap;
  1451.  
  1452.     va_start(ap);
  1453.     (void)fprintf(stderr, "PANIC(%s): ", exitcode);
  1454.     (void)vfprintf(stderr, fmt, ap);
  1455.     putc('\n', stderr);            /* fatal messages not \n terminated */
  1456.     va_end(ap);
  1457.  
  1458.     return_to_sender = TRUE;
  1459.     exit(exitcode);
  1460. }
  1461.  
  1462. #endif    /* STANDALONE */
  1463.